﻿using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

namespace ns
{
    public class SortSolution : MonoBehaviour
    {
        //冒泡排序
        public static void bubbleSort_1(int[] arr)
        {
            for (int i = 0; i < arr.Length - 1; i++) //代表轮次循环
            {
                for (int j = 0; j < arr.Length - i - 1; j++) //代表组内循环
                {
                    if (arr[j] > arr[j + 1]) //如果左边的数大于右边的数，且不使用中间变量进行交换
                    {
                        arr[j + 1] = arr[j + 1] + arr[j];
                        arr[j] = arr[j + 1] - arr[j]; //arr[j] 和 arr[j+1]进行了交换
                        arr[j + 1] = arr[j + 1] - arr[j];
                    }
                }
            }
        }

        public static void bubbleSort_2(int[] arr)
        {
            bool is_Swapped = true; //判断排序是否启动的条件
            for (int i = 0; i < arr.Length - 1; i++) //代表轮次循环
            {
                if (!is_Swapped) break; //如果没有发生交换，说明剩余部分已经有序
                is_Swapped = false; //先设置为false
                for (int j = 0; j < arr.Length - i - 1; j++) //代表组内循环
                {
                    if (arr[j] > arr[j + 1]) //如果左边的数大于右边的数，且不使用中间变量进行交换
                    {
                        arr[j + 1] = arr[j + 1] + arr[j];
                        arr[j] = arr[j + 1] - arr[j]; //arr[j] 和 arr[j+1]进行了交换
                        arr[j + 1] = arr[j + 1] - arr[j];
                        is_Swapped = true; //发生了交换，设置启动条件
                    }
                }
            }
        }


        public static void bubbleSort_3(int[] arr)
        {
            //优化:添加一个上次交换的索引
            bool is_Swapped = true;
            int lastSortIndex = arr.Length - 1;
            int swappedIndex = -1;
            while (is_Swapped) //控制外圈循环
            {
                is_Swapped = false;
                for (int i = 0; i < lastSortIndex; i++) //控制组内循环
                {
                    if (arr[i] > arr[i + 1]) //如果左边的数大于右边的数，且不使用中间变量进行交换
                    {
                        arr[i + 1] = arr[i + 1] + arr[i];
                        arr[i] = arr[i + 1] - arr[i]; //arr[j] 和 arr[j+1]进行了交换
                        arr[i + 1] = arr[i + 1] - arr[i];
                        is_Swapped = true; //发生了交换，设置启动条件
                        swappedIndex = i; //交换的最后一次索引位置
                    }
                }
                lastSortIndex = swappedIndex; // 最后一个没有经过排序的元素的下标就是最后一次发生交换的位置，控制组内循环结束位置
            }
        }

        //选择排序
        public static void SelectionSort_1(int[] arr)
        {
            int minIndex;//需要一个最小值索引下标
            for (int i = 0; i < arr.Length - 1; i++)
            {
                minIndex = i; //每一个位置的最小值从头开始
                for (int j = i + 1; j < arr.Length; j++)
                {
                    if (arr[minIndex] > arr[j]) //当前最小值位置 > J位置
                    {
                        minIndex = j;//记录最新的最小值位置,循环结束后最后得出最小值位置
                    }
                }
                //交换当前位置和最小值位置
                arr[minIndex] = arr[minIndex] + arr[i];
                arr[i] = arr[minIndex] - arr[i]; //现在当前位置变为最小值
                arr[minIndex] = arr[minIndex] - arr[i]; //把原先的最小值位置交换到前面
            }
        }

        public static void SelectionSort_2(int[] arr)
        {
            int minIndex, maxIndex;//需要一个最小值索引下标,和最大值索引下标
            for (int i = 0; i < arr.Length / 2; i++) //循环范围减少一半
            {
                minIndex = maxIndex = i; //每一个位置的最小值最大值从头开始
                for (int j = i + 1; j < arr.Length; j++)
                {
                    if (arr[minIndex] > arr[j]) //当前最小值位置 > J位置
                    {
                        minIndex = j;//记录最新的最小值位置,循环结束后最后得出最小值位置
                    }
                    if (arr[maxIndex] < arr[j]) //当前最大值位置 < J位置
                    {
                        minIndex = j;//记录最新的最小值位置,循环结束后最后得出最小值位置
                    }
                }
                if (maxIndex == minIndex) break; //如果最大值和最小值下标是相同的，说明已经排好序了

                //交换当前位置和最小值位置
                arr[minIndex] = arr[minIndex] + arr[i];
                arr[i] = arr[minIndex] - arr[i]; //现在当前位置变为最小值
                arr[minIndex] = arr[minIndex] - arr[i]; //把原先的最小值位置交换到前面

                if (maxIndex == i) maxIndex = minIndex; //I已经和minIndex交换过位置，如果maxIndex和I相同，就进行和MinIndex
                int lastIndex = arr.Length - i - 1; //把最大值交换到最后面
                arr[maxIndex] = arr[maxIndex] + arr[lastIndex];
                arr[lastIndex] = arr[maxIndex] - arr[lastIndex];
                arr[maxIndex] = arr[maxIndex] - arr[lastIndex];
            }
        }

        //插入排序
        public static void InsertSort_1(int[] arr)
        {
            for (int i = 1; i < arr.Length; i++) //循环，从第二个开始，往前插入数值
            {
                int curIdx = i; //记录当前索引值
                while (curIdx >= 1 && arr[curIdx] < arr[curIdx - 1]) //当前数值比之前小，就交换，一直循环，前面完全排序
                {
                    arr[curIdx] = arr[curIdx] + arr[curIdx - 1];
                    arr[curIdx - 1] = arr[curIdx] - arr[curIdx - 1];
                    arr[curIdx] = arr[curIdx] - arr[curIdx - 1];
                    curIdx--; //更新当前索引值，向前一位
                }
            }
        }

        public static void InsertSort_2(int[] arr)
        {
            for (int i = 0; i < arr.Length; i++)
            {
                for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) // 比较当前数字和前一个数字，
                {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
            }
        }

        ////快速排序框架
        //public static void QuickSort(int[] arr)
        //{
        //   QuickSort(arr, 0, arr.Length - 1);
        //}
        //public static void QuickSort(int[] arr, int start, int end)
        //{
        //    // 将数组分区，并获得中间值的下标
        //    int middle = Partition(arr, start, end);
        //    // 对左边区域快速排序
        //    QuickSort(arr, start, middle - 1);
        //    // 对右边区域快速排序
        //    QuickSort(arr, middle + 1, end);
        //}
        //public static int Partition(int[] arr, int start, int end)
        //{
        //    // TODO: 将 arr 从 start 到 end 分区，左边区域比基数小，右边区域比基数大，然后返回中间值的下标
        //    return 0;
        //}


        public static void QuickSort(int[] arr)
        {
            QuickSort(arr, 0, arr.Length - 1);
        }
        public static void QuickSort(int[] arr, int start, int end)
        {
            // 如果区域内的数字少于 2 个，退出递归
            if (start >= end) return;
            // 将数组分区，并获得中间值的下标
            int middle = Partition(arr, start, end);
            // 对左边区域快速排序
            QuickSort(arr, start, middle - 1);
            // 对右边区域快速排序
            QuickSort(arr, middle + 1, end);
        }
        // 将 arr 从 start 到 end 分区，左边区域比基数小，右边区域比基数大，然后返回中间值的下标
        public static int Partition(int[] arr, int start, int end)
        {

            int pivot = arr[start]; // 取第一个数为基数
            int left = start + 1;  // 左边界，从第二个数开始分区
            int right = end;      // 右边界
            while (left < right)
            {
                while (left < right && arr[left] <= pivot) left++; // 找到第一个大于基数的位置                
                while (left < right && arr[right] >= pivot) right--; // 找到第一个小于基数的位置
                // 交换这两个指针，使得左边分区都小于或等于基数，右边分区大于或等于基数
                if (left < right)
                {
                    exchange(arr, left, right);
                    left++;
                    right--;
                }
            }
            // 如果 left 和 right 相等，单独比较 arr[right] 和 pivot
            if (left == right && arr[right] > pivot) right--;
            // 将基数和轴交换
            exchange(arr, start, right);
            return right;
        }
        private static void exchange(int[] arr, int i, int j)
        {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

        //三数取中法
        private void Partition(int[] nums, int start, int end, int k)
        {
            if (start >= end) return;

            int middle = start + (end - start) / 2; //中间索引值

            SwapIfGreater(nums, start, end); //交换最大值在右边，最小值在左边
            SwapIfGreater(nums, middle, start); //交换
            SwapIfGreater(nums, middle, end);

            int pivot = nums[start]; //基数数值选择第一个

            int i = start;
            int j = end;

            while (i < j)
            {
                while (i < j && nums[j] >= pivot) { --j; }
                while (i < j && nums[i] <= pivot) { ++i; }
                if (i < j) { Swap(nums, i, j); }
            }

            Swap(nums, start, i);

            if (i > k) { Partition(nums, start, i - 1, k); }
            else if (i < k) { Partition(nums, i + 1, end, k); }
        }

        private void SwapIfGreater(int[] nums, int i, int j)
        {
            if (i != j)
            {
                if (nums[i] > nums[j])
                {
                    Swap(nums, i, j);
                }
            }
        }

        private void Swap(int[] nums, int i, int j)
        {
            if (i != j)
            {
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }




        //归并排序，需要额外空间result
        public static void MergeSort(int[] array)
        {
            if (array.Length == 0) return;
            int[] result = new int[array.Length];
            MergeSort(array, 0, array.Length - 1, result);
        }
        //1、划分左右区域
        private static void MergeSort(int[] arr, int start, int end, int[] result)
        {
            int middle = start + (end - start) / 2;
            MergeSort(arr, start, middle, result);   //划分左边区域
            MergeSort(arr, middle + 1, end, result); //划分右边区域
            Merge(arr, start, end, result); //归并左右区域
        }
        //2、归并左右区域
        private static void Merge(int[] arr, int start, int end, int[] result)
        {
            int start1 = start;
            int end1 =  (end + start) / 2;
            int start2 = end1 + 1;
            int end2 = end;
            //遍历左右数组的指针
            int idx1 = start;
            int idx2 = start2;
            while (idx1<=end1 && idx2 <=end2) //一直循环，直到result数组填充完毕
            {
                if (arr[idx1] <= arr[idx2]) //往result数组里添加数据
                    result[idx1 + idx2 - start2] = arr[idx1++]; //先赋值，在自增
                else
                    result[idx1 + idx2 - start2] = arr[idx2++]; //先赋值，在自增
            }
            while (idx1<=end1) //将剩余的数字补到结果数组里
            {
                result[idx1 + idx2 - start2] = arr[idx1++]; //先赋值，在自增
            }
            while (idx2 <= end2) //将剩余的数字补到结果数组里
            {
                result[idx1 + idx2 - start2] = arr[idx2++]; //先赋值，在自增
            }
            while (start<=end) //将结果数组copy到arry中，以便下次比较
            {
                arr[start] = result[start];
                start++;
            }
        }
    }

}
